package com.jn.algorithm.day019.question57;

import java.util.*;

/**
 * @author 江南大学1033190417
 * @date 2022/5/10 21:40
 */
public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        Deque<int[]> res = new ArrayDeque<>();
        boolean flag = true, used = false;
        if (intervals[0][0] > newInterval[1]) {
            res.addLast(newInterval);
            used=true;
        }
        res.addLast(intervals[0]);
        for (int i = 0; i < intervals.length; i++) {
            int[] last = res.getLast();
            int[] now = intervals[i];
            if (now[1] < newInterval[0] || now[0] > newInterval[1]) {
                if (i > 0) {
                    res.addLast(now);
                }
                if (i!= intervals.length-1&&newInterval[1]<intervals[i+1][0]&&!used){
                    res.addLast(newInterval);
                    used=true;
                }
                flag = false;
            } else {
                if (!flag) {
                    res.addLast(now);
                    last = now;
                    flag = true;
                }
                last[0] = Math.min(Math.min(last[0], newInterval[0]), now[0]);
                last[1] = Math.max(Math.max(last[1], newInterval[1]), now[1]);
            }
        }
        int[] last = res.getLast();
        if (last[1] < newInterval[0]) {
            res.addLast(newInterval);
        }
        return res.toArray(new int[res.size()][]);
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] intervals = new int[][]{
                {3, 5},
                {12, 15},
//                {6, 7},
//                {8, 10},
//                {12, 16}
        };
        int[] newInterval = new int[]{6, 6};
        int[][] insert = solution.insert(intervals, newInterval);
        for (int[] t : insert) {
            System.out.println(Arrays.toString(t));
        }
    }
}
